import collections
from typing import List


class Solution:
    def __init__(self):
        self.cache = collections.defaultdict(int)  # 记忆化递归缓存

    def removeBoxes(self, boxes: List[int]) -> int:
        return self.recur(boxes)

    def recur(self, boxes):
        # 当前已没有剩下的盒子了
        if len(boxes) <= 1:
            self.cache[tuple(boxes)] = len(boxes)
            return len(boxes)

        # 当前盒子情况在缓存中
        if tuple(boxes) in self.cache:
            return self.cache[tuple(boxes)]

        # 统计和开头的连续相同颜色的盒子数量
        flag = 0
        for i in boxes:
            if i == boxes[0]:
                flag += 1
            else:
                break

        # 统计所有与开头盒子一样颜色的盒子的下标
        sav = []
        for i in range(len(boxes)):
            if boxes[i] == boxes[0]:
                sav.append(i)

        # 计算取走开头所有连续颜色的盒子的积分
        ans = flag * flag + self.recur(boxes[flag:])

        # 计算先取走中间部分的盒子的积分
        for i in sav:
            if i < flag:
                continue
            ans = max(ans, self.recur(boxes[:flag] + boxes[i:]) + self.recur(boxes[flag:i]))

        # 将结果存储到记忆化递归
        self.cache[tuple(boxes)] = ans
        return self.cache[tuple(boxes)]


if __name__ == "__main__":
    print(Solution().removeBoxes([1, 3, 2, 2, 2, 3, 4, 3, 1]))  # 23

    print(Solution().removeBoxes([1, 1, 1]))  # 9
    print(Solution().removeBoxes([1]))  # 1

    # 测试用例20
    print(Solution().removeBoxes(
        [1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2,
         2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 1,
         1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1]))  # 2758

    # 自制用例
    print(Solution().removeBoxes([1, 2, 3, 4, 5, 6, 1, 6, 5, 4, 3, 2, 1]))  # 25
